<!DOCTYPE html>

<html>
<head>
    <meta charset="utf-8" />
    <title>TopCoder TCCC 2003 Semifinals 2 - 1050: TelephoneGame</title>
    
    <link type="image/x-icon" rel="shortcut icon" href="http://www.topcoder.com/i/favicon.ico"/>
    

    
    <style type="text/css">
        /* font */
body {
    font-family: Helvetica, Arial, Verdana, sans-serif;
    font-size: 16px;
    line-height: 1.2em;
}
ul.constraints > li:before, ul.notes > li:before {
    font-family: monospace;
    font-weight: normal;
}
.heading {
    font-weight: bold;
    font-size: 175%;
    line-height: 1.2em;
}
.section .section-title {
    font-weight: bold;
    font-size: 125%;
}
ol.testcases > li:before {
    font-family: monospace;
}
type {
    font-weight: bold;
    font-family: monospace;
}
li.testcase .data {
    font-family: monospace;
    line-height: 1.5em;
}

/* layout */
.heading {
    margin-top: 0.1em;
    margin-bottom:0.1em;
    text-align: center;
}
.section .section-title {
    margin-top : 1em;
    margin-bottom: 1em;
}
.problem-intro, note, user-constraint {
    padding-left: 1.25em;
}

/* Lists */
ul.constraints, ul.notes, ul.variables, ul.problem-definition-lines {
    list-style-type: none;
    padding: 0px;
}
ul.constraints > li:before {
    content: "-";
    position:relative;
    margin-left: 0px; /* optional, for multiline li element */
    left: 0.625em;
}
ul.notes > li:before {
    content: "-";
    position:relative;
    margin-left: 0px; /* optional, for multiline li element */
    left: 0.625em;
}

/* Testcases */
li.testcase {
    line-height: 1.1em;
    padding-top: 0.625em;
    padding-bottom: 0.625em;
    overflow: auto;
}
li.testcase > .testcase-content > div { padding-bottom: 0.5em; padding-left: 1em; }

li.testcase .testcase-comment {
    margin: 0;
    padding-left: 1em;
}
.testcase-comment p:first-child { margin-top: 0; }
.testcase-comment p:last-child { margin-bottom: 0; }

li.testcase .testcase-content {
    margin: 0.31em;
}

/* Data and variables */
.testcase-output {
    padding: 0.2em 1em 0.2em 0em;
}
.variables, .testcase-output {
    margin-left: 0.5em;
    display: table;
    margin-bottom: 0px;
    margin-top: 0px;
}
.variable {
    display: table-row;
}
.variable .name {
    padding: 0.2em 0em 0.2em 1em;
    font-weight: bold;
    display: table-cell;
    text-align: right;
}
.testcase-output .prefix {
    padding: 0.2em 0em 0.2em 1em;
    display: table-cell;
}
.testcase-output .prefix:after {
    content : ":";
    padding-right: 0.5em;
}
.variable .name:after {
    font-weight: bold;
    content : ":";
    padding-right: 0.5em;
}
.variable .value, .testcase-output .value {
    padding: 0.2em 1em 0.2em 0em;
    display: table-cell;
}
ol.testcases {
    padding: 0px;
    counter-reset: test_number -1;
}
ol.testcases > li {
    list-style:none;
}
ol.testcases > li:before {
    counter-increment:test_number;
    display: block;
    clear: both;
    content:counter(test_number) ")";
    color: inherit;
    background: inherit;
}

/* Problem Definition */
.problem-definition, .problem-limits {
    padding-left: 1.25em;
}
.problem-definition-lines, .limit-lines {
    display: table;
    margin-top: 0px;
    margin-bottom: 0px;
    padding-left: 0px;
}
.definition-line, .limit-line {
    display: table-row;
    height: 1.5em;
    overflow: auto;
}
.limit-name:after {
    content: ":";
    margin-right: 1em;
}
.definition-name, .definition-value, .limit-name, .limit-value {
    display: table-cell;
}
.definition-value {
    padding-left: 0.5em;
}
.definition-name:after {
    content: ":";
}
#contest-division:before {
    content: "Div ";
}
#problem-score:before {
    content: "- Problem ";
}
#problem-name {
    display: block;
}

/* Tags, hidden default */
.tag {
    visibility: hidden;
    position: absolute;
}

        body {
    /* font color */
    color: #333333;
    /* background color */
    background-color: white;
}
.section .section-title {
    /* title color */
    color: black;
}
li.testcase .data {
    /* highlight color */
    background: #eee;
}

    </style>
    
    
    

</head>

<body>
    <h1 class="heading">
        <span id='contest-name'>TCCC 2003 Semifinals 2</span>
        
        <span id='problem-score'>1050</span>
        <span id='problem-name'>TelephoneGame</span>
    </h1>

    <hr />

    <!-- Problem Statement -->
    <div class="section">
        <h2 class="section-title">Problem Statement</h2>
        <div class="problem-intro">
            <intro>A bunch of people in a large park area are setting up a telephone network using receivers directly connected by wires.  There is a lot of spare wire, so the connections need not be straight.  The only restriction on the medium is that there be no crossings, since they could cause interference.  In other words, if observed from a helicopter above the park, none of the wires can appear to be crossing over one another.  Initially, the group of people set up a base network where person 0 is connected to person 1, person 1 is connected to person 2, ..., person <i>i</i> is connected to person <i>i</i>+1, ..., and the last person is connected back to person 0 forming a cycle. Afterwards many other connections were built.  The problem is, some of the new connections may have forced crossings to occur.<br />
<br />
Given the additional connections that were formed, your method will determine the minimum number of connections that need be removed such that there will not be any crossings.  Note that, given a particular set of connections, if it is possible to lay the wires such that they will not cross, the people will do so.  This means the people may change their locations and how much wire they use in order to remove crossings.  They will not succeed if a crossing is inevitable.  Also, since the base network must not be damaged, the removed connections cannot include any of the base network connections.<br />
<br />
You will be given 2 <type>int[]</type>s <b>connect1</b> and <b>connect2</b> representing the additional connections formed.  If the <i>k</i>th elements of <b>connect1</b> and <b>connect2</b> are <i>a</i> and <i>b</i> respectively, person <i>a</i> and person <i>b</i> have formed a connection.  Note, connections are symmetric, so if <i>a</i> and <i>b</i> are connected then <i>b</i> and <i>a</i> are connected.  You will also be given an <type>int</type> <b>numPeople</b> representing the number of people forming the network.  Each element of <b>connect1</b> and <b>connect2</b> will be integers between 0 and <b>numPeople</b>-1 inclusive.</intro>
        </div>
    </div>
    
    <!-- Problem definition -->
    
    <div class="section" id="definition">
        <h2 class="section-title">Definition</h2>
        <div class="problem-definition">
            <ul class="problem-definition-lines">
                <li class="definition-line" id='class-line'>
                    <span class='definition-name'>Class</span>
                    <span class='definition-value'>TelephoneGame</span>
                </li>
                <li class="definition-line" id='method-line'>
                    <span class='definition-name'>Method</span>
                    <span class='definition-value'>howMany</span>
                </li>
                <li class="definition-line" id='parameters-line'>
                    <span class='definition-name'>Parameters</span>
                    <span class='definition-value'>
                    
                        tuple(integer)
                    , 
                        tuple(integer)
                    , 
                        integer
                    
                    </span>
                </li>
                <li class="definition-line" id='returns-line'>
                    <span class='definition-name'>Returns</span>
                    <span class='definition-value'>
                        integer
                    </span>
                </li>
                <li class="definition-line" id='signature-line'>
                    <span class='definition-name'>Method signature</span>
                    <span class='definition-value'>
                        def howMany(self, connect1, connect2, numPeople)
                    </span>
                </li>
            </ul>
            <div class="problem-definition-public-tip">(be sure your method is public)</div>
        </div>        
    </div>
    

    <!-- Limits -->
    <div class="section">
        <h2 class="section-title">Limits</h2>
        <div class='problem-limits'>
            <ul class="limit-lines">
                <li class='limit-line'>
                    <span class='limit-name'>Time limit (s)</span>
                    <span class='limit-value'>2.000</span>
                </li>
                <li class='limit-line'>
                    <span class='limit-name'>Memory limit (MB)</span>
                    <span class='limit-value'>64</span>
                </li>
            </ul>
        </div>
    </div>

    
    <!-- Notes -->
    <div class="section">
        <h2 class="section-title">Notes</h2>
        <ul class="notes">
        
            <li><note>Without loss of generality, you can assume that the people are arranged in a circular pattern.  Continuing this image, the base network would be seen from a helicopter as a circle.</note></li>
        
        </ul>
    </div>
    
    
    <!-- Constraints -->
    <div class="section">
        <h2 class="section-title">Constraints</h2>
        <ul class="constraints">
        
            <li><user-constraint><b>connect1</b> must contain between 1 and 18 elements inclusive</user-constraint></li>
        
            <li><user-constraint><b>connect1</b> must contain the same number of elements as <b>connect2</b></user-constraint></li>
        
            <li><user-constraint><b>numPeople</b> must be between 4 and 10000 inclusive</user-constraint></li>
        
            <li><user-constraint>Element <i>i</i> of <b>connect1</b> will not be equal to element <i>i</i> of <b>connect2</b></user-constraint></li>
        
            <li><user-constraint>Each element of <b>connect1</b> and <b>connect2</b> will be between 0 and <b>numPeople</b>-1 inclusive</user-constraint></li>
        
            <li><user-constraint>There will be no repeated connections.  In other words, if a connection from <i>a</i> to <i>b</i> exists, there will be no other connections of the form <i>a</i> to <i>b</i> or <i>b</i> to <i>a</i> allowed as input.  This includes the original connections, so there will be no connections from <i>i</i> to <i>i+1</i>, or from 0 to the last person.</user-constraint></li>
        
        </ul>
    </div>

    <!-- Test cases -->
    <div class="section">
        <h2 class="section-title">Test cases</h2>
        <ol class="testcases" start='0'>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">connect1</span>
                                <span class="value data">
                                
                                    { 0, 1 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">connect2</span>
                                <span class="value data">
                                
                                    { 2, 3 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">numPeople</span>
                                <span class="value data">
                                
                                    4
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            0
                        
                        </span>
                    </div>
                    
                    <div class="testcase-annotation">
                        <div class='tag'>note</div>
                        <div class="testcase-comment">The given connections can easily be formed without crossings as depicted below:<pre>
  _______
 /       |
0---1   /
|  /|  / 
| / | /  
|/  |/   
3---2
</pre></div>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">connect1</span>
                                <span class="value data">
                                
                                    { 4, 4, 4, 5, 5, 6 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">connect2</span>
                                <span class="value data">
                                
                                    { 6, 7, 8, 7, 8, 8 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">numPeople</span>
                                <span class="value data">
                                
                                    10
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            1
                        
                        </span>
                    </div>
                    
                    <div class="testcase-annotation">
                        <div class='tag'>note</div>
                        <div class="testcase-comment">There is no way for all of these connections to be added without a crossing.</div>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">connect1</span>
                                <span class="value data">
                                
                                    { 0, 2, 4 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">connect2</span>
                                <span class="value data">
                                
                                    { 3, 5, 1 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">numPeople</span>
                                <span class="value data">
                                
                                    6
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            1
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">connect1</span>
                                <span class="value data">
                                
                                    { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">connect2</span>
                                <span class="value data">
                                
                                    { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">numPeople</span>
                                <span class="value data">
                                
                                    100
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            0
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
            <li class="testcase">
                <div class="testcase-content">
                    <div class="testcase-input">
                        <div class='tag'>input</div>
                        <ul class="variables">
                        
                            <li class="variable data">
                                <span class="name data">connect1</span>
                                <span class="value data">
                                
                                    { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">connect2</span>
                                <span class="value data">
                                
                                    { 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47 }
                                
                                </span>
                            </li>
                        
                            <li class="variable data">
                                <span class="name data">numPeople</span>
                                <span class="value data">
                                
                                    1000
                                
                                </span>
                            </li>
                        
                        </ul>
                    </div>
                    <div class="testcase-output">
                        <div class='tag'>output</div>
                        <span class="prefix data">Returns</span>
                        <span class="value data">
                        
                            16
                        
                        </span>
                    </div>
                    
               
                </div>
            </li>
            
        </ol>
    </div>
    <hr />

    This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
</body>
</html>
